package com.LeetCode.Array;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * 计算右侧小于当前元素的个数
 */
public class CountLeftSmaller {

    int[] index;//索引堆
    int[] count;//存放结果
    int[] helper;//辅助空间

    public List<Integer> countSmaller(int[] nums) {
        int len = nums.length;
        index = new int[len];
        count = new int[len];
        helper = new int[len];
        for(int i = 0; i<len; i++){
            index[i] = i;
        }
        megreCount(nums, 0, len-1);

        List<Integer> res = new ArrayList<>();

        for(int i = 0; i<len; i++){
            res.add(count[i]);
        }

        return res;
    }

    public void megreCount(int[] nums, int l, int r){
        if(l >= r)
            return;
        int mid = (l+r)>>>1;

        megreCount(nums, l, mid);
        megreCount(nums, mid + 1, r);

        int i = l, j = mid + 1;
        int k = l;
        while(i <= mid && j <= r){
            if(nums[index[i]] <= nums[index[j]]){
                helper[k++] = index[j++];
            }else{
                count[index[i]] += r - j + 1;
                helper[k++] = index[i++];
            }
        }

        while(i <= mid) helper[k++] = index[i++ ];
        while(j <= r) helper[k++] = index[j++];

        for(int start = l; start <= r; start++){
            index[start] = helper[start];
        }
    }

    @Test
    public void test(){
        System.out.println(countSmaller(new int[]{0,2,1}));
    }
}
